package _220320;

import java.util.Scanner;

/**
 * @author ShadowLim
 * @create 2022-03-20-9:16
 */
public class _一步之遥 {

    /**
     * 暴力
     * @param args
     */
//    public static void main(String[] args) {
//        Scanner scanner = new Scanner(System.in);
//        for (int i = 1; i < 100; i++) {
//            for (int j = 1; j < 100; j++) {
//                if (97 * i - 127 * j == 1) {
//                    System.out.println(i + j);
//                    break;
//                }
//            }
//        }
//        scanner.close();
//    }



    static int x, y;

    /** 246ms
     * 参考：https://blog.csdn.net/Void_worker/article/details/79672544
     *  「扩展欧几里得算法」
     *  根据题目列出方程：97 * x - 127 * y = 1，这是一个不定方程，要求不定方程的整数解，用扩展欧几里得算法。
     * 「扩展欧几里得算法是用来在已知a,b求解一组x,y,使它们满足贝祖等式：ax + by = gcd(a,b) = d
     * (解一定存在，根据数论中的相关定理)」
     * 扩展欧几里得算法推导：
     *      Ax + By = gcd(A,B)                                  （1）
     *    ->Ax + By = gcd(B,A%B)
     *     (A = B * (A / B) + A % B （用B来表示A）)
     *    ->(B * (A / B) + A % B) x + By = gcd(B,A%B)
     *    -> B * (A / B * x + y) + (A % B) * x = gcd(B, A %B)   （2）
     *  解出方程（2）的解为x1,y1,（1）与（2）形式对应，所以
     *  x1 = (A / B * x + y), y1 = x
     *  所以 x = y1, y = x1 - A / B * y1;
     *
     * @param args
     */
    public static void main(String[] args) {
        // 97x - 127y == 1
        gcd_xy(97, -127);
        System.out.println(Math.abs(x) + Math.abs(y));
    }

    private static int gcd_xy(int a, int b) {
        if (b == 0) {
            x = 1;
            y = 0;
            return a;
        }
        int ans = gcd_xy(b, a % b);
        int t = y;
        y = x - (a / b) * y;
        x = t;
        return ans;
    }
}
